package 周赛;

import java.util.Arrays;

public class 最小化目标值与所选元素的差 {

    public int minimizeTheDifference(int[][] mat, int target) {
        //由提示可知此数组最多可以得到的最大值为70×70,为了方便设置为5000
        int MAX = 5000;
        int row = mat.length;
        //定义动规方程;dp[i][j]表示第i行是否可以取到值为j
        //转移方程为dp[i][j] = dp[i][j] | dp[i - 1][j - val]; val为当前位置的值
        boolean[][] dp = new boolean[row][MAX];
        //初始化;第一行全部可以到达，初始化为true
        for (int j : mat[0]) {
            dp[0][j] = true;
        }

        for (int i = 1; i < row; i++) {
            for (int val : mat[i]) {
                for (int j = val; j < MAX; j++) {
                    dp[i][j] = dp[i][j] | dp[i - 1][j - val];
                }
            }
        }

        //从最后一行可以取到的值里找绝对差最小
        int res = Integer.MAX_VALUE;
        for (int j = 0; j < MAX; j++) {
            if (dp[row - 1][j]) {
                res = Math.min(res, Math.abs(j - target));
            }
        }
        return res;
    }
}
